#include "pch.h"

#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#include <vector>

#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
	struct DataModelX {
		std::vector<double> weights;
		std::vector<int> quantities;
		int num_items;
		int num_bins;
		int bin_capacity;
	};

	void BinPacking(DataModelX data, const std::string& solver_id) {
		// Create the mip solver with the SCIP backend.
		std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver(solver_id));

		if (!solver) {
			std::cout << solver_id << " solver unavailable.\n";
			return;
		}
		std::vector<std::vector<const MPVariable*>> x(data.num_items, std::vector<const MPVariable*>(data.num_bins));
		for (int i = 0; i < data.num_items; ++i) {
			for (int j = 0; j < data.num_bins; ++j) {
				x[i][j] = solver->MakeIntVar(0.0, data.quantities[i], "");
			}
		}
		// y[j] = 1 if bin j is used.
		std::vector<const MPVariable*> y(data.num_bins);
		for (int j = 0; j < data.num_bins; ++j) {
			y[j] = solver->MakeIntVar(0.0, 1.0, "");
		}

		// Create the constraints.
		// Each item is in exactly one bin.
		for (int i = 0; i < data.num_items; ++i) {
			LinearExpr sum;
			for (int j = 0; j < data.num_bins; ++j) {
				sum += x[i][j];
			}
			solver->MakeRowConstraint(sum == data.quantities[i]);
		}
		// For each bin that is used, the total packed weight can be at most
		// the bin capacity.
		for (int j = 0; j < data.num_bins; ++j) {
			LinearExpr weight;
			for (int i = 0; i < data.num_items; ++i) {
				weight += data.weights[i] * LinearExpr(x[i][j]);
			}
			solver->MakeRowConstraint(weight <= LinearExpr(y[j]) * data.bin_capacity);
		}

		// Create the objective function.
		MPObjective* const objective = solver->MutableObjective();
		LinearExpr num_bins_used;
		for (int j = 0; j < data.num_bins; ++j) {
			num_bins_used += y[j];
		}
		objective->MinimizeLinearExpr(num_bins_used);
		const MPSolver::ResultStatus result_status = solver->Solve();

		// Check that the problem has an optimal solution.
		if (result_status != MPSolver::OPTIMAL) {
			std::cout << "The problem does not have an optimal solution!";
			return;
		}
		std::cout << "Number of bins used: " << objective->Value() << std::endl
			<< std::endl;
		double total_weight = 0;
		for (int j = 0; j < data.num_bins; ++j) {
			if (y[j]->solution_value() == 1) {
				std::cout << "Bin " << j << std::endl << std::endl;
				double bin_weight = 0;
				for (int i = 0; i < data.num_items; ++i) {
					if (x[i][j]->solution_value() > 0) {
						//std::cout << "Item " << i << " - Weight: " << data.weights[i] << "-count: " << x[i][j]->solution_value() << std::endl;
						bin_weight += data.weights[i] * x[i][j]->solution_value();
					}
				}
				//std::cout << "Packed bin weight: " << bin_weight << std::endl << std::endl;
				total_weight += bin_weight;
			}
		}
		std::cout << "Total packed weight: " << total_weight << std::endl;
	}
} // namespace operations_research

void TimerRunSlv(operations_research::DataModelX data, const std::string& solver_id) {
	const auto start = std::chrono::high_resolution_clock::now();
	operations_research::BinPacking(data, solver_id);
	const auto end = std::chrono::high_resolution_clock::now();
	const auto duration = std::chrono::duration_cast<std::chrono::duration<double, std::milli>>(end - start);
	std::cout << solver_id << ", calc " << data.weights.size() << ",use " << duration <<std::endl;
}

TEST(taoliao, cbc) {
	operations_research::DataModelX dm;
	std::vector<double> partLens_100 = {
		11, 949, 692, 743, 90, 327, 152, 633, 801, 888, 793, 698, 354, 921, 454, 319, 763, 474, 894, 397, 346, 545, 166, 393, 763, 433, 813, 239, 253, 959, 716, 779, 241, 889, 163, 725, 737, 237, 402,
		401, 865, 535, 165, 743, 802, 867, 183, 270, 615, 41, 943, 111, 714, 807, 98, 236, 600, 536, 10, 239, 703, 1000, 58, 246, 968, 901, 148, 261, 482, 528, 543, 446, 91, 589, 968, 630, 687, 454,
		399, 689, 71, 532, 52, 492, 625, 87, 818, 808, 442, 398, 717, 671, 392, 543, 34, 844, 405, 666, 39, 223
	};
	std::vector<double> partLens_200 = {
		73, 470, 457, 507, 265, 298, 471, 497, 331, 959, 718, 571, 5, 795, 487, 507, 604, 657, 971, 32, 355, 992, 129, 222, 821, 129, 896, 977, 771, 885, 498, 490, 344, 381, 278, 396, 582, 204, 751,
		265, 44, 565, 726, 908, 694, 218, 164, 684, 733, 449, 356, 727, 341, 776, 398, 11, 138, 46, 984, 510, 226, 234, 469, 766, 254, 549, 734, 742, 822, 549, 130, 139, 520, 524, 535, 140, 0, 635,
		847, 102, 733, 547, 962, 141, 745, 957, 463, 338, 630, 272, 463, 288, 113, 682, 385, 533, 353, 764, 38, 634, 186, 278, 995, 520, 965, 922, 109, 149, 467, 560, 138, 507, 778, 316, 843, 463,
		194, 234, 316, 965, 547, 525, 629, 885, 355, 96, 698, 393, 482, 741, 632, 717, 846, 398, 19, 245, 550, 11, 471, 155, 284, 324, 549, 779, 41, 232, 23, 569, 760, 308, 615, 857, 217, 937, 425,
		34, 542, 947, 337, 325, 916, 893, 213, 54, 789, 769, 750, 229, 490, 66, 118, 577, 454, 595, 933, 31, 818, 821, 812, 99, 760, 937, 314, 290, 992, 421, 846, 772, 417, 715, 990, 628, 550, 130,
		449, 855, 186, 673, 488, 739
	};

	std::vector<double> partLens_300 = {
		708, 277, 61, 375, 229, 947, 645, 298, 289, 298, 30, 368, 237, 300, 985, 663, 380, 396, 339, 561, 749, 779, 896, 224, 839, 912, 93, 779, 146, 248, 728, 690, 614, 913, 636, 91, 484, 33, 777,
		952, 475, 944, 958, 364, 845, 341, 564, 739, 45, 338, 362, 844, 189, 323, 127, 195, 898, 613, 3, 791, 286, 607, 91, 854, 13, 241, 217, 606, 289, 869, 297, 172, 469, 43, 642, 919, 959, 330,
		372, 524, 580, 374, 34, 943, 21, 623, 334, 459, 279, 444, 235, 51, 800, 470, 820, 528, 752, 568, 309, 609, 932, 810, 587, 837, 243, 348, 529, 85, 240, 777, 187, 480, 432, 539, 582, 624, 443,
		456, 216, 813, 834, 735, 531, 414, 33, 392, 616, 182, 180, 830, 977, 820, 555, 927, 646, 52, 565, 489, 719, 692, 453, 174, 50, 138, 561, 703, 430, 262, 1000, 56, 94, 542, 690, 643, 30, 389,
		711, 573, 783, 130, 205, 188, 175, 132, 580, 22, 291, 173, 93, 437, 58, 846, 941, 217, 861, 744, 581, 339, 398, 936, 306, 450, 957, 14, 92, 300, 640, 155, 427, 37, 682, 780, 570, 688, 400,
		707, 316, 211, 216, 545, 879, 416, 238, 65, 987, 605, 751, 377, 530, 64, 225, 822, 881, 426, 911, 691, 492, 21, 89, 621, 676, 547, 955, 835, 429, 654, 14, 237, 449, 795, 93, 659, 439, 791,
		217, 804, 423, 49, 545, 948, 775, 393, 971, 247, 717, 469, 767, 792, 535, 114, 526, 415, 953, 239, 183, 192, 709, 973, 245, 82, 926, 405, 129, 479, 137, 627, 751, 75, 797, 830, 307, 343, 38,
		352, 445, 797, 671, 857, 755, 487, 907, 349, 576, 935, 792, 238, 228, 29, 780, 384, 246, 18, 39, 813, 597, 896, 490, 583, 407, 565
	};
	std::vector<int> counts1 = {
		12, 12, 36, 12, 12, 12, 36, 12, 12, 24, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 24, 12, 60, 48, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 24, 12, 12, 12
	};
	std::vector<int> counts2 = {
		1, 1, 3, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1
	};

	std::vector<int> counts3 = {

	};
	double gap = 2.0;
	double len = 6000;
	double liu_bian = 3;
	double jie_duan = 140;
	for (auto& part_len : partLens_300) {
		part_len += gap;
		counts3.push_back(1);
	}
	dm.weights = partLens_300;
	dm.quantities = counts3;
	dm.num_bins = dm.weights.size();
	dm.num_items = dm.weights.size();
	dm.bin_capacity = len - liu_bian - jie_duan;
	TimerRunSlv(dm, "SCIP");
	TimerRunSlv(dm, "BOP");
	TimerRunSlv(dm, "CP_SAT");
	TimerRunSlv(dm, "GLOP");
	// TimerRunSlv(dm, "GLPK_MIP");
	// TimerRunSlv(dm, "CBC");
}
